package cn.cxq.learning.tree;

/**
 * 二叉排序树
 */
public class BinarySortTree {

    private BinarySortNode root;

    /**
     * 中序遍历（正好是升序）
     */
    public void inorderTransversal(){
        if (this.root==null) System.out.println("二叉排序树为空~~~");
        else this.root.inorderTransversal();
    }

    public void add(BinarySortNode binarySortNode){
        if (this.root == null){
            this.root = binarySortNode;
        }

        else this.root.add(binarySortNode);
    }

    public BinarySortNode search(int value){
        if (this.root == null) {
            return null;
        }

        return this.root.search(value);
    }

    public BinarySortNode searchParent(int value){
        if (this.root == null || this.root.left == null&&this.root.right == null) {
            return null;
        }
        return this.root.searchParent(value);
    }

    public void delete(int value){
        if (this.root == null) {
            return;
        }
        if (this.root.left == null&&this.root.right == null) {
            if (this.root.value == value) this.root = null;
            return;
        }
        BinarySortNode node = search(value);
        BinarySortNode parent = searchParent(value);
        if (node.left == null && node.right == null) {
            if (parent.left == node) parent.left = null;
            else parent.right = null;
        }else if (node.left != null && node.right == null){
            if (parent.left == node) parent.left = node.left;
            else parent.right = node.left;
        }else if (node.left == null && node.right != null){
            if (parent.left == node) parent.left = node.right;
            else parent.right = node.right;
        }else {
            BinarySortNode min = node.findMin();

            delete(min.value);

            node.value = min.value;
        }
    }
}

class BinarySortNode{

    int value;
    BinarySortNode left;
    BinarySortNode right;

    public BinarySortNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "BinarySortNode{" +
                "value=" + value +
                '}';
    }

    public void inorderTransversal(){

        if (this.left!= null) this.left.inorderTransversal();

        System.out.println(this);

        if (this.right!= null) this.right.inorderTransversal();
    }

    public void add(BinarySortNode binarySortNode) {
        if (this.value>binarySortNode.value) {
            if (this.left == null) this.left = binarySortNode;
            else this.left.add(binarySortNode);
        }
        else{
            if (this.right == null) this.right = binarySortNode;
            else this.right.add(binarySortNode);
        }
    }

    public BinarySortNode search(int value) {

        if (this.value == value) return this;
        else if (this.value > value){
            if (this.left == null) return null;
            return this.left.search(value);
        }else {
            if (this.right == null) return null;
            return this.right.search(value);
        }
    }

    public BinarySortNode searchParent(int value) {
        if ((this.left!= null&&this.left.value == value) || (this.right!=null&&this.right.value == value)) return this;
        if (this.value>value) {
            if (this.left!=null) return this.left.searchParent(value);
            return null;
        } else {
            if (this.right!=null) return this.right.searchParent(value);
            return null;
        }
    }

    /**
     * 返回子树中最小节点
     * @return
     */
    public BinarySortNode findMin() {
        BinarySortNode temp = this;
        while (temp.left!=null) temp = temp.left;

        return temp;
    }
}